package leetcode.editor.week.week304;

public class Solution6134 {
    // 图论太菜
    // 题目：https://leetcode.cn/problems/find-closest-node-to-given-two-nodes/
    // 解析：https://leetcode.cn/problems/find-closest-node-to-given-two-nodes/solution/-by-wa-pian-d-slci/

    // 第一个人走，记录走过节点的步数
    // 第二个人走，记录走过节点的步数
    // 对2个人走过的所有点收集答案，能到达且步数最小
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;

        // 使用包装类作为区别，由于0代表可以走到自己，null代表没走过
        Integer[] been1 = new Integer[n];   // 第一个人走过的步数
        int cur = node1; // 当前节点
        int cut = 0; // 步数
        while (cur != -1 && been1[cur] == null) {
            been1[cur] = cut++;
            cur = edges[cur];
        }

        Integer[] been2 = new Integer[n];   // 第二个人走过的步数
        cur = node2; // 当前节点
        cut = 0; // 步数
        while (cur != -1 && been2[cur] == null) {
            been2[cur] = cut++;
            cur = edges[cur];
        }

        // 枚举每一个节点
        int res = -1, maxCut = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            // 如果两个都走过
            if (been1[i] != null && been2[i] != null) {
                // 题目要求：较大值最小化
                // 慢的就是这个位置的答案
                int max = Math.max(been1[i], been2[i]);
                // 取最小的
                if (max < maxCut) {
                    maxCut = max;
                    res = i;
                }
            }
        }

        return res;
    }
}
